Skip to main content

226. Invert Binary Tree

문제​

Given the root of a binary tree, invert the tree, and return its root.

예제 입출력​

img

Input: root = [4,2,7,1,3,6,9]
Output: [4,7,2,9,6,3,1]
info

You can read the full description here.

풀이 1​

접근법​

  1. 원래 노드를 전위순회하면서, 반대 방향으로 새로운 노드를 만듭니다.
  2. 원래 노드와 새로운 노드를 매개변수로 가져가고, 새로운 매개변수는 빈 노드로 넣어줍니다.

구현 코드​

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        result: Optional[TreeNode] = None

        def preorder(original_node: Optional[TreeNode], inverted_node: Optional[TreeNode]):
            if original_node == None:
                return

            inverted_node.val = original_node.val

            if original_node.left:
                inverted_node.right = TreeNode()
                preorder(original_node.left, inverted_node.right)

            if original_node.right:
                inverted_node.left = TreeNode()
                preorder(original_node.right, inverted_node.left)

            return

        if root:
            result = TreeNode()
            preorder(root, result)

        return result

복잡도 분석​

  • nn: 노드의 수
  • 시간복잡도: O(n)O(n)

책에 있는 풀이​

info

원본 코드는 여기에서 확인하실 수 있습니다.

풀이 2​

접근법​

  1. 전체 알고리즘을 좌우반전 후위순회하면서 두 자식노드를 스왑합니다.

구현 코드​

class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        if root:
            root.left, root.right = \
                self.invertTree(root.right), self.invertTree(root.left)
            return root
        return None

복잡도 분석​

  • nn: 노드의 수
  • 시간복잡도: O(n)O(n)

풀이 3​

접근법​

  1. BFS로 순회하게 되면 depth 단계별로 순회가 가능합니다. BFS로 순회하면서 하위 노드를 스왑합니다.

구현 코드​

class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        queue = collections.deque([root])

        while queue:
            node = queue.popleft()
            # 부모 노드 부터 하향식 스왑
            if node:
                node.left, node.right = node.right, node.left

                queue.append(node.left)
                queue.append(node.right)

        return root

복잡도 분석​

  • nn: 노드의 수
  • 시간복잡도: O(n)O(n)

풀이 4​

접근법​

  1. 풀이 3의 큐를 스택으로 바꾸면 DFS 순회가 됩니다.

구현 코드​

class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        stack = collections.deque([root])

        while stack:
            node = stack.pop()
            # 부모 노드 부터 하향식 스왑
            if node:
                node.left, node.right = node.right, node.left

                stack.append(node.left)
                stack.append(node.right)

        return root

복잡도 분석​

  • nn: 노드의 수
  • 시간복잡도: O(n)O(n)

풀이 5​

접근법​

  1. DFS 후위 순회 방식으로 스왑합니다.

구현 코드​

class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        stack = collections.deque([root])

        while stack:
            node = stack.pop()

            if node:
                stack.append(node.left)
                stack.append(node.right)

                node.left, node.right = node.right, node.left  # 후위 순회

        return root

복잡도 분석​

  • nn: 노드의 수
  • 시간복잡도: O(n)O(n)